#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

// https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/?envType=daily-question&envId=2025-06-06
// 2434. 使用机器人打印字典序最小的字符串

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<char> nextMin(n + 1);
        nextMin[n] = 'z';

        for (int i = n - 1; i >= 0; i--){
            nextMin[i] = min(nextMin[i + 1], s[i]);
        }

        stack<char> myStack;
        string ans;
        for (int i = 0; i < n; i++){
            myStack.push(s[i]);
            while(!myStack.empty() && myStack.top() <= nextMin[i + 1]){
                ans += myStack.top();
                myStack.pop();
            }
        }
        return ans;
    }
};

int main()
{
    string s = "bac";
    Solution solution{};
    cout << solution.robotWithString(s) << endl;
    return 0;
}